package cn.suchan.jianzhi.q32_array;

import java.util.ArrayList;
import java.util.TreeSet;

/**
 * 知识点：把数组排成最小的数
 * 题目描述
 * 输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。
 * 例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。
 *
 * @author suchan
 * @date 2019/05/31
 */
public class Solution {

    /**
     * 直接使用q27那道题的解决方法，其实这两道题的本质还是排列组合
     *
     * @param numbers
     * @return
     */
    public String PrintMinNumber(int[] numbers) {
        if (numbers == null || numbers.length <= 0) {
            return "";
        }

        ArrayList<String> result = new ArrayList<>();
        // 用于排序输出(可以直接排好序)
        TreeSet<String> res = new TreeSet<>();
        getResult(numbers, 0, numbers.length - 1, res);
        result.addAll(res);
        return result.get(0);
    }

    public void getResult(int[] numbers, int start, int end, TreeSet<String> res) {
        if (start == end) {
            String result = "";
            for (int i = 0; i < numbers.length; i++) {
                result += numbers[i];
            }
            res.add(result);
        } else {
            for (int i = start; i <= end; i++) {
                //交换位置
                swap(numbers, start, i);
                //递归  这个递归捋得我好累啊
                getResult(numbers, start + 1, end, res);
                //System.out.println("start==>" + start + " & i==>" + i + " & end==>" + end);
                //再把位置换回来，保证下次换位是正确的
                swap(numbers, start, i);
                //System.out.println("==============================");
                //System.out.println("start==>" + start + " & i==>" + i + " & end==>" + end);
            }
        }
    }

    /**
     * 交换位置
     *
     * @param numbers
     * @param a
     * @param b
     */
    public void swap(int[] numbers, int a, int b) {
        if (a != b) {
            int temp = numbers[a];
            numbers[a] = numbers[b];
            numbers[b] = temp;
        }
    }


    public String PrintMinNumber1(int[] numbers) {
        if (numbers == null || numbers.length <= 0) {
            return "";
        }
        for (int i = 0; i < numbers.length - 1; i++) {
            for (int j = i + 1; j < numbers.length; j++) {
                int temp1 = Integer.valueOf(numbers[i] + "" + numbers[j]);
                int temp2 = Integer.valueOf(numbers[j] + "" + numbers[i]);

                if (temp2 < temp1) {
                    int temp = numbers[i];
                    numbers[i] = numbers[j];
                    numbers[j] = temp;
                }
            }
        }

        String min = "";
        for (int i = 0; i < numbers.length; i++) {
            min += numbers[i];
        }
        return min;
    }

    public static void main(String[] args) {
        int[] numbers = {3, 32, 321};

        Solution solution = new Solution();
        System.out.println(solution.PrintMinNumber1(numbers));
    }
}
